import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    // leetcode hot 100 三数之和
    // https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
    public List<List<Integer>> threeSum(int[] nums) {
        // 首先固定一个数，然后剩下的两个数使用双指针来遍历，两个指针分别从最左边和最右边遍历
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        if (len < 3 || nums[0] > 0 || nums[len-1] < 0) return ret;
        for (int i = 0; i < len-2; i++) {
            if (nums[i] > 0) break;
            if (i != 0 && nums[i] == nums[i-1]) continue;
            int left = i + 1, right = len - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == -nums[i]) {
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while (right > left && nums[right-1] == nums[right]) {
                        right--;
                    }
                    while (left < right && nums[left] == nums[left+1]) {
                        left++;
                    }
                    left++;
                    right--;
                }
                else if (sum > -nums[i]) {
                    right--;
                }
                else if (sum < -nums[i]) {
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] arr = {-1,0,1,2,-1,-4};
        ThreeSum threeSum = new ThreeSum();
        threeSum.threeSum(arr);
        System.out.println(666);
    }
}
